In general, there are several known techniques for designing a physical network comprised of a plurality of nodes interconnected by a plurality of links. Several constraints or requirements must be taken into consideration in designing a network. A few of these constraints include the “diameter” of a network, the “node degree” of any node, the immunity to the failure of a single node or link, etc. Given a set of network designs that satisfy the constraints mentioned above, the “objective function” or “metric” used to rank the designs is the total number of links, which we want to be as small as possible. In telecom applications, this means we want to find the network design using the fewest fiber optic cables. Every telecommunications service provider who builds physical networks faces this problem. The problem is particularly difficult to solve when the number of nodes is large, the network diameter is required to be small, and the maximum node degree is also required to be small. Yet these are exactly the conditions facing a telecom service provider, since a service provider must have equipment in many locations to service customers, must provide a low diameter network to keep the delay low on all connections, and must have a small maximum node degree to keep equipment costs low.
There is a lack of methods to solve large network design problems that incorporate the constraints mentioned above. Many existing methods are unpredictable, in that they are heuristics, which may perform poorly. Other existing methods are designed to produce the optimal answer, but are totally impractical for large problems, since they would take hours or days to run on a computer. Therefore, there is a need of an efficient method of designing a low cost network that satisfies these constraints.